/*
 * @lc app=leetcode.cn id=105 lang=swift
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution105 {
    // 从前序与中序遍历序列构造二叉树
    // 从前序获得根
    // 从中序获得左右子树
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        return  build(preorder, inorder, preStart: 0, preEnd: preorder.count - 1, inStart: 0, inEnd: inorder.count - 1)
    }
    func build(_ preorder: [Int],
                _ inorder: [Int],
                preStart: Int,
                preEnd: Int,
                inStart: Int,
                inEnd: Int) -> TreeNode? {
        guard preStart <= preEnd else {
            return nil
        }
        guard inStart <= inEnd else {
            return nil
        }
        let rootValue = preorder[preStart]
        let rootNode = TreeNode(rootValue)
        // 左边节点的个数
        var leftCount = 0
        // 当前根节点index
        var rootIndex = inEnd
        for i in inStart...inEnd {
            if inorder[i] == rootValue {
                leftCount = i - inStart
                rootIndex = i
                break
            }
        }
        // 递推的去构建子树
        let left = build(preorder, inorder, preStart: preStart + 1, preEnd: preStart + leftCount, inStart: inStart, inEnd: rootIndex - 1)
        
        let right = build(preorder, inorder, preStart: preStart + leftCount + 1, preEnd: preEnd, inStart: rootIndex + 1, inEnd: inEnd)
    
        rootNode.left = left
        rootNode.right = right
        return rootNode
    }
    
    static func test(){
        let preorder = [3,9,20,15,7]
        let inorder = [9,3,15,20,7]
        let solution = Solution105()
        let root = solution.buildTree(preorder, inorder)
        print(root)
    }
}
// @lc code=end

